package test5;

import java.util.Arrays;
import java.util.Scanner;

public class Solution2 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入石头数量：");
        int num = sc.nextInt();
        int[] stones = new int[num];
        System.out.println("请输入石头重量：");
        for (int i = 0; i < num; i++) {
            stones[i] = sc.nextInt();
        }
        int result = lastStoneWeightII(stones);
        System.out.println("剩下石头最小的可能重量为：" + result);
    }
    private static int lastStoneWeightII(int[] stones) {
        int sum = 0;
        for (int stone : stones) {
            sum += stone;
        }
        int capacity = sum / 2;//背包容量为总量的一半
        int[] dp = new int[capacity + 1];
        dp[0] = 0;
        for (int stone : stones) {//物品
            for (int j = capacity; j >= stone; j--) {//背包大小必须大于物品大小
                dp[j] = Math.max(dp[j], dp[j - stone] + stone);
            }
        }
        return sum - 2 * dp[capacity];
    }
}
